package LeetCode刷题;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-06 16:04
 * @description: Functions of this class is
 * 官方题解：
 **/
public class No路径总和III和二叉树中和为某一值的路径 {
    public static void main(String[] args) {

    }
      public static  class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            List<List<Integer>> ans=new ArrayList();
            if(root!=null){
                List<Integer>sub=new ArrayList();

                dfs(root,0,target,sub,ans);
            }
            return ans;
        }
        private void dfs(TreeNode cur,int tot,int target,List<Integer>sub,List<List<Integer>> ans){
            if(cur==null){
                return;
            }
            sub.add(cur.val);//把节点加入到子集集合中
            tot+=cur.val;
            if((cur.left==null&&cur.right==null)&&tot==target){
                //如果有叶子节点存在的话，就不能只是根节点的值
                ans.add(new ArrayList<Integer>(sub));
//                return;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!这里千万不能提前退出，不然会影响后面的回溯，因为缺少了remove这一步！！！！！！！！！！！！
            }
            dfs(cur.left,tot,target,sub,ans);//一直向左递归，
            //如果找不到的话就递归回溯

            dfs(cur.right,tot,target,sub,ans);//然后向右递归
            //如果找不到的话就递归回溯
            tot-=cur.val;//tot减去当前节点的值
            sub.remove(sub.size()-1);//集合中去除

        }
    }
}